š Problem Statement
In a high-performance wireless communication grid, there are N signal towers aligned in a straight line. Each tower broadcasts a signal with varying strength, recorded once per day. To evaluate network stability, engineers must frequently analyze segments of the grid to identify the most reliable zones for stable coverage.
Given a range of towers [L, R] and a fixed segment length K, the engineers must determine the minimum of all maximum signal strengths over every K-length subsegment within [L, R].
To support this analysis efficiently, you are required to use a Sparse Table to preprocess the signal strength data for fast Range Maximum Queries.
š„ Input Format
- First line:
NandK(number of towers and subsegment length) - Second line:
Nspace-separated integers (signal strengths, 1 ā¤ strength ā¤ 100) - Third line:
Q(number of queries, 1 ā¤ Q ā¤ 20) - Next
Qlines: Two integersLandR(0 ā¤ L ā¤ R ā K + 1 < N)
š¤ Output Format
For each query, output a single integer representing the minimum of all K-length segment maximums in the range [L, R].
šÆ Sample Test Case 1
8 3 60 72 55 80 65 90 50 78 2 0 4 2 5
72 80
- Query [0, 4] with K=3:
- Segment [0,2]: {60,72,55} ā max = 72
- Segment [1,3]: {72,55,80} ā max = 80
- Segment [2,4]: {55,80,65} ā max = 80
- Result: min(72, 80, 80) = 72
- Query [2, 5] with K=3:
- Segment [2,4]: {55,80,65} ā max = 80
- Segment [3,5]: {80,65,90} ā max = 90
- Result: min(80, 90) = 80
šÆ Sample Test Case 2
10 4 88 95 70 85 60 92 76 80 69 74 2 1 6 3 9
92 80
š§ Sparse Table with Sliding Window
This problem combines Sparse Table for Range Maximum Query (RMQ) with a sliding window technique to find the minimum among all K-length segment maximums.
š Two-Phase Approach
Phase 1: Build Sparse Table - Preprocess the array for O(1) range maximum queries
Phase 2: Sliding Window - For each query [L, R], slide a K-length window and use the sparse table to find the maximum in each window, then return the minimum of these maximums
š§ Phase 1: Building Sparse Table (for MAX)
// Initialize for length 1 (2^0)
for (int i = 0; i < n; i++) {
sparse[i][0] = arr[i];
}
// Build for increasing powers of 2
for (int j = 1; (1 << j) <= n; j++) {
for (int i = 0; i + (1 << j) <= n; i++) {
sparse[i][j] = max(sparse[i][j-1],
sparse[i + (1 << (j-1))][j-1]);
}
}
sparse[i][j] = maximum value in range starting at index i with length 2^j
š Phase 2: Query with Sliding Window
// Query maximum in range [L, R] using sparse table
int queryMax(int L, int R) {
int length = R - L + 1;
int k = log2(length);
return max(sparse[L][k],
sparse[R - (1 << k) + 1][k]);
}
// Main query: Find min of all K-segment maxs in [L, R]
int solve(int L, int R, int K) {
int minOfMaxs = INT_MAX;
// Slide window of size K from L to R-K+1
for (int i = L; i <= R - K + 1; i++) {
int segmentMax = queryMax(i, i + K - 1);
minOfMaxs = min(minOfMaxs, segmentMax);
}
return minOfMaxs;
}
ā” Complexity Analysis
- Build: O(n log n) - construct sparse table once
- Per Query: O(R-L) - slide window and query in O(1) each time
- Total: O(n log n + Q Ć n) - much better than O(Q Ć n Ć K) naive
š” Key Insights
- Sparse Table enables O(1) range maximum queries using overlapping power-of-2 ranges
- For range [L, R], we can find max using two overlapping ranges of length 2^k where k = floor(log2(R-L+1))
- The sliding window examines exactly (R - L - K + 2) segments of length K
- We're looking for the minimum stability point - the K-segment with the smallest peak signal
šÆ Visual Example
Array: [60, 72, 55, 80, 65], K=3, Query [0, 4]
Window 1 [0,2]: max(60, 72, 55) = 72 Window 2 [1,3]: max(72, 55, 80) = 80 Window 3 [2,4]: max(55, 80, 65) = 80 Result: min(72, 80, 80) = 72 ā